Codeforces Round #592 Div2 A~E 题解

闲话

C好难,D好水.本场链接:Codeforces Round #592

A. Pens and Pencils

题目大意:一根钢笔可以写cc篇文章,一根铅笔可以画dd张画,最多只能带kk支笔.要写aa篇文章,画bb幅画.问是否可以完成,如果可以,输出带的钢笔和铅笔的数量.
数据范围:
1a,b,c,d,k1001 \leq a,b,c,d,k \leq 100

思路

至少要有上取整的a/ca/c根钢笔和上取整的b/db/d根铅笔,加起来不到kk就满足.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		int a,b,c,d,k;scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
		int l = ceil(double(a) / c);
		int r = ceil(double(b) / d);
		if(l + r > k)	puts("-1");
		else printf("%d %d\n",l,r);
    }
    return 0;
}

B. Rooms and Staircases

原题大意:有一个2n2*n的棋盘,棋盘上下不是全部相连的,上下的相连关系由一个字符串SS给出,如果Si=1S_i=1说明第ii位上下的格子是联通的.现在有一个机器人,你可以任意指定他的初始位置,并且不能经过之前已经经过的边,问你最多能走过多少个格子.

数据范围:
1n10001 \leq n \leq 1000

错解思路

显然如果能转向就转向,这个时候每一个11都可以给我提供22个的步数,如果不能转向,那就是11的贡献.直接扫描统计字符串即可.错了的原因是,初始位置是不固定的,而且不能简单地就这样统计00的步数,如果另一边可以绕一圈过来,就可能导致字符串位置上虽然是00,但是实际这一列的贡献是22的情况.

正解思路

很显然,如果我转向了一次,之后是可以再转回来的,如果我从最左端出发,那么走到一个最远的11之后绕一圈,这样的距离步数是最大的.于是可以统计最左端和最右端的11的位置,分别乘22表示我绕了一圈,统计答案即可.如果没有11那就只能走一条直线,答案为nn.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1005;
char s[N];
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		int n;scanf("%d",&n);
		scanf("%s",s + 1);getchar();
		int res = 0,L = 0x3f3f3f3f,R = -1;
		for(int i = 1;i <= n;++i)	
		{
			if(s[i] == '1')	
				L = min(L,i),R = max(R,i);
		}
		if(R == -1)	
		{
			printf("%d\n",n);
			continue;
		}
		res = max({res,L * 2,(n - L + 1) * 2});
		res = max({res,R * 2,(n - R + 1) * 2});
		printf("%d\n",res);
    }
    return 0;
}

C. The Football Season

题目大意:解不定方程:
{xw+yd=px+y+z=n0x,y,z\begin{cases}x*w+y*d=p\\x+y+z=n\\ 0 \leq x,y,z \end{cases}
其中x,y,zx,y,z是未知数,其余已知.
求出一组解即可.

数据范围:
1n10121 \leq n \leq 10^{12}
0p10170 \leq p \leq 10^{17}
1d<w1051 \leq d < w \leq 10^5

错解思路

这题要的就是找一个x+yx+y最小的解,因为x+yx+y越小留给zz的空间就越大,如果最小值都比nn大则无解,那求不定方程,直接上exgcdexgcd.错就错在数据范围太大了,如果直接exgcdexgcd显然会导致爆long long.

正解思路

想要知道怎么找x+yx+y的最小的解的,一是消元,二是可以从方程入手:
不定方程xw+dy=px*w + d*y = p本身是没什么信息的,可以想办法等价变形,找出各个解的形式:
原式=xw+dw+dydw=p=x*w + d*w + d*y - d*w = p
=(x+d)w+(yw)d=p=(x + d)*w + (y - w)*d=p
故不定方程的解都满足x+kdx + k*d以及ykwy - k*w的形式.因为w>dw > d,所以yy减小的速度比xx增大的速度快,进而如果yy达到最小,那么x+yx+y也就达到了最小.而所有的yy满足ykwy-kw这个形式,所以最终答案的最小的yy的取值范围就是[0,w)[0,w).这一点是比较好想的,又注意到w105w \leq10^5所以可以直接枚举yy的取值,如果合法就直接输出,全部都不合法就说明无解,因为最小的都不够用,就不可能有更好的情况了.另外有一个博客也是讲这个问题,推荐一下:关于ax+by=c的解x,y的min(|x|+|y|)值问题

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
	ll n,p,w,d;cin >> n >> p >> w >> d;
	ll sres = 0,resx = -1,resy = -1;
	for(ll y = 0;y < w;++y)
	{
		ll A = p - d * y;
		if(A % w == 0)
		{
			ll x = A / w;
			if(x >= 0 && x + y <= n)
			{
				cout << x << " " << y << " " << n - x - y << endl;
				return 0;
			}
		}
	}
	cout << "-1";
    return 0;
}

D. Paint the Tree

题目大意:有一个nn点的无根树,给定每个节点染成某种颜色的代价.颜色只有三种,要求树上三个相连的节点颜色是不能相同的.求是否能染色这棵树,如果能,求出最小代价.

数据范围:
1n1051 \leq n \leq 10^5
1cost1091 \leq cost \leq 10^9

思路

首先考虑什么时候无解:对于某一个点来说,如果与他相连的点达到33个或以上,就无解.这一点应该是很显然的,因为一旦连了33个点必然会导致颜色相同,因此整颗树上不存在一个度数为33的点.这就意味着:这棵树退化成了一个链.这是一个非常强的条件.找到了这个条件之后整个题就变得简单了:因为对于一个链来说,如果他的首/尾和与之相连的颜色确定了,那么整个链的颜色也就确定了.
首先找到一个度数为11的点,标记成根节点.枚举根节点和与之相邻的点的颜色,然后直接dfsdfs确定整个链的代价.并记录代价和具体方案,统计一下即可.
注意权值很大,会爆int.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+7;
int cost[3][N],deg[N],n,col[N],rescol[N];
vector<int> edges[N];
ll res;
void dfs(int u,int fa,int c1,int c2)
{
	for(auto& v : edges[u])
	{
		if(v == fa)	continue;
		int c = 3 - c1 - c2;
		res += cost[c][v];
		col[v] = c;
		dfs(v,u,c2,c);
	}
}
int main()
{
	scanf("%d",&n);
	for(int i = 0;i < 3;++i)
		for(int j = 1;j <= n;++j)
			scanf("%d",&cost[i][j]);
   	int root = 1,ok = 1;
   	for(int i = 1;i < n;++i)
   	{
   		int u,v;scanf("%d%d",&u,&v);
   		edges[u].push_back(v);++deg[u];
   		edges[v].push_back(u);++deg[v];
   	}
   	for(int i = 1;i <= n;++i)
   	{
   		if(deg[i] >= 3)
   		{
   			ok = 0;
   			break;
   		}
   		else if(deg[i] == 1)	root = i;
   	}
   	if(!ok)	puts("-1");
   	else
   	{
   		ll reres = 0x3f3f3f3f3f3f3f3f;
   		for(int i = 0;i < 3;++i)
   		{
   			for(int j = 0;j < 3;++j)
   			{
   				if(j == i)	continue;
   				res = cost[i][root] + cost[j][edges[root].back()];
   				col[root] = i;col[edges[root].back()] = j;
   				// cout << res << "*";
   				dfs(edges[root].back(),root,i,j);
   				// cout << i << " " << j << " " << res << endl;
   			   	if(reres > res)
	   			{
	   				reres = res;
	   				for(int i = 1;i <= n;++i)	rescol[i] = col[i];
	   			}
   			}
   		}
   		printf("%lld\n",reres);
   		for(int i = 1;i <= n;++i)	printf("%d ",rescol[i] + 1);
   	}
    return 0;
}

E. Minimizing Difference

题目大意:给定一个长度为nn的序列,定义diff值为最大值和最小值的差值.你可以给序列里的任意一个元素加一或减一最多kk次,问最小的diff值是多少.

数据范围:
2n1052 \leq n \leq 10^5
1k10141 \leq k \leq 10^{14}
1ai1091 \leq a_i \leq 10^9

思路

一开始应该能想到大概贪心直接构造是不行的,但是可以二分答案xx判断xx是否是答案.不过这个题就难在怎么写checkcheck框架上了.
如果答案是xx的话,说明序列里所有的数都应该[p,p+x]\in [p,p+x]这个区间,那么这个区间的取值有个特点,pp或者p+xp+x这两个数之间一定有一个数是aa里的值,因为如果两者都不是的话,等价的减少到序列里的值,可以使答案减小,因此一定是有一个的.于是checkcheck就是在做两种分支:一种是以当前的aia_i作为pp另一种是以当前的aia_i作为p+xp+x进行判断.
假如整个序列里最后一个比pp小的元素是ala_l,第一个比p+xp+x大的元素是ara_r.那么修改次数就是左边和右边的部分加起来就行了.即修改次数=pli=1lai(p+x)(nr+1)+i=rnai=p*l - \sum^l_{i=1} a_i - (p+x) * (n - r + 1) + \sum^n_{i=r} a_i,求和部分可以前缀和.
最后考虑怎么找ppp+xp+x.首先对于aia_ipp的情况,要找的就是一个ajai>=xa_j - a_i >= x的最大的jj之后的一位(额外加一位,使得ajai>xa_j - a_i > x).其次对于aia_ip+xp + x的情况,要找的就是一个aiaj>=xa_i - a_j >= x的最小的一位.注意对于这两种情况而言,对应的ppp+xp+x不一定是aja_j.比如前者的p+xp+x实际上是ai+xa_i+x,后者的pp实际上是aixa_i-x.最后看答案是不是合法的就行了.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+7;
ll n,k,a[N],s[N];
bool check(int x)
{
	for(int i = 1,j = 1;i <= n;++i)
	{
		while(j <= n && a[j] - a[i] <= x)	++j;
		if(a[i] * (i - 1) - s[i - 1] + s[n] - s[j - 1] - (a[i] + x) * (n - j + 1) <= k)	return 1;
	}
	for(int i = 1,j = 1;i <= n;++i)
	{
		while(a[i] - a[j] > x)	++j;
		if((a[i] - x) * (j - 1) - s[j - 1] + s[n] - s[i] - a[i] * (n - i) <= k)	return 1;
	}
	return 0;
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
    cin >> n >> k;
    for(int i = 1;i <= n;++i)	cin >> a[i];
    sort(a + 1,a + 1 + n);
    for(int i = 1;i <= n;++i)	s[i] = s[i - 1] + a[i];
    int l = 0,r = a[n],res;
    while(l < r)
    {
    	int mid = l + r >> 1;
    	if(check(mid))	r = mid;
    	else l = mid + 1;
    }
    printf("%d",l);
    return 0;
}